package heap;

public class SkewHeap<T extends Comparable<T>> {

    private SkewNode<T> mRoot;

    private class SkewNode<T extends Comparable<T>>{
        T data;
        SkewNode<T> left;
        SkewNode<T> right;

        public SkewNode(T data, SkewNode<T> left, SkewNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "SkewNode{" +
                    "data=" + data +
                    '}';
        }
    }

    public SkewHeap(){
        mRoot = null;
    }

    private void preOrder(SkewNode<T> heap){
        if(heap!=null){
            System.out.println(heap.data+" ");
            preOrder(heap.left);
            preOrder(heap.right);
        }
    }

    public void preOrder(){
        preOrder(mRoot);
    }

    private void inOrder(SkewNode<T> heap){
        if(heap!=null){
            inOrder(heap.left);
            System.out.println(heap.data+" ");
            inOrder(heap.right);
        }
    }

    public void inOrder(){
        inOrder(mRoot);
    }

    private void postOrder(SkewNode<T> heap){
        if(heap!=null){
            postOrder(heap.left);
            postOrder(heap.right);
            System.out.println(heap.data+" ");
        }
    }

    public void postOrder(){
        postOrder(mRoot);
    }

    private SkewNode<T> merge(SkewNode<T> x,SkewNode<T> y){
        if(x == null)return y;
        if(y == null)return x;

        if(x.data.compareTo(y.data)>0){
            SkewNode<T> tmp = x;
            x = y;
            y = tmp;
        }

        SkewNode<T> tmp = merge(x.right,y);
        x.right = x.left;
        x.left = tmp;
        return x;
    }


    public void merge(SkewHeap<T> other){
        this.mRoot = merge(this.mRoot,other.mRoot);
    }

    public void insert(T data){
       SkewNode<T> node = new SkewNode<T>(data,null,null);
       this.mRoot = merge(this.mRoot,node);
    }

    public T remove(){
        if(mRoot == null)
            return null;

        T data = this.mRoot.data;

        SkewNode<T> l = mRoot.left;
        SkewNode<T> r = mRoot.right;
        this.mRoot = merge(l,r);
        return data;
    }
}
